package code;

public class 剑指offer09 {
    /***
     * 1、用链表来存储队列比较容易，但是会多余一些存储信息（next）。
     */
    class CQueue_1 {
        element head,tail;
        public CQueue_1() {
            head=tail=null;
        }

        public void appendTail(int value) {
            element node=new element(value);
            if(tail==null){
                head=tail=node;
            }else{
                tail.next=node;
                tail=node;
            }
        }

        public int deleteHead() {
            int res;
            if(head==null){
                return -1;
            }else if(head==tail){
                res=head.data;
                head=tail=null;
            }else{
                res=head.data;
                head=head.next;
            }
            return res;
        }
        class element{
            int data;
            element next;
            element(int data){
                this.data=data;
                next=null;
            }
        }
    }
    class CQueue_2 {
        /***
         * 用滚动数组实现循环队列，当head=tail时候为空，当（head+2）%MAXLEN的时候为full
         */
        int[] data=new int[10000];
        int head,tail;
        final  int MAXLEN=10000;
        public CQueue_2() {
            head=tail=0;
        }
        public void appendTail(int value) {
            if((tail+2)%MAXLEN==head){
                System.out.println("已经full了");
            }else{
                data[tail]=value;
                tail=(tail+1)%MAXLEN;
            }
        }
        public int deleteHead() {
            if(head==tail){
                return -1;
            }else{
                head=(head+1)%MAXLEN;
            }
            return data[(head-1+MAXLEN)%MAXLEN];
        }
    }
    class CQueue {
        /****
         * 3、使用双栈进行模拟队列，一个作为插入，一个作为删除。
         * 时间复杂度：插入是O（1），删除：但是仔细考虑下，如果某次move带来了x个元素从stack1中移出，那么这个x个元素的移出复杂度总和为O（x），那么均摊的复杂度为O（1）
         * 空间复杂度：
         */
        stack s1=new stack(10000);
        stack s2=new stack(10000);
        public CQueue() {

        }
        public void appendTail(int value) {
            s1.push(value);
        }
        public void move(stack s1,stack s2){
            while(s1.size()>0){
                s2.push(s1.pop());
            }
        }
        public int deleteHead() {
            if(s2.size()>0){
                return s2.pop();
            }else if(s1.size()>0){
                move(s1,s2);
                return s2.pop();
            }else{
                return -1;
            }
        }
        class stack{
            int[] data;
            int top=0;
            stack(int size){
                data=new int[size];
            }
            void push(int value){
                data[top++]=value;
            }
            int pop(){
                if(top-1<0){
                    return -1;
                }
                return data[--top];
            }
            int size(){
                return top;
            }
        }
    }
    public static void main(String[] args) {

    }
}
